# -*- coding:utf-8 -*-
"""
Created on Apr 12, 2011

@author: Lithuanian
"""
from algorithm import Heuristic
from math import sqrt

class pile2robot(Heuristic):
    
    #to turn DEBUG prints ON, set DEBUG to True
    DEBUG = False
    
    def evaluate(self, problem_state):
        return self.calculate(problem_state.robots, \
                problem_state.dirt_locations, problem_state.width, \
                problem_state.height)
            
    def calculate(self, robots, piles, width, height):
        S = height*width
        k = float(height)/width
        #robot area height and width
        h = int(sqrt(height))
        w = int(h/k)
############DEBUG############
        if self.DEBUG:        
            print "h: " + str(h)
            print "w: " + str(w)
            print "k: " + str(k)
##############################        
        #dictinary. (row,col) => problemSquare
        squars = {}
        
        rowNum = height/h
        colNum = width/w
############DEBUG############
        if self.DEBUG:
            print "colnum: " + str(colNum)
            print "rownum: " + str(rowNum)
##############################
        #create problem squars
        for row in xrange(0,rowNum):
            for col in xrange(0, colNum):
                xEnd = col*w + w
                yEnd = row*h + h
                if col == colNum:
                    xEnd = width
                if row == rowNum:
                    yEnd = height
                #add problem square to the dctionary
                squars[self.hashKeys(col*w,row*h)] = problemSquare(col*w, row*h, xEnd, yEnd)
############DEBUG############
        if self.DEBUG:
            print "Squares: " + str(squars.keys())
            print "Key len: " + str(len(squars.keys()))
############################## 
        #add robots to problem squars
        for robot in robots:
############DEBUG############
            if self.DEBUG:
                print "robot: " + str(robot)
############################## 
            squars[self.calcSqure(robot[0],robot[1], w, h, width, height)].robots.add(robot)
            
        
        #add piles to problem square
        for pile in piles:
############DEBUG############
            if self.DEBUG:
                print "pile: " + str(pile)
##############################
            squars[self.calcSqure(pile[0],pile[1], w, h, width, height)].piles.add(pile)
        
        #calculate heuristic values
        hVal = 0
        manDist = 0
        for square in squars.values():
            #calulate Heuristic value as the sum of square values
            hVal += square.calcSquareValue(float(len(piles))/len(robots))
            #calculate mannhaten distance
            dist = square.pile2RobotManDist()
            if dist == -1:
                #no piles but there are robots
                for pile in piles:
                    dist = distToClosestPile(square.robots, piles)  
            
            manDist += dist
        
#        delta = (width + height)/2
        delta = 1
        return manDist + delta*hVal
    
    def hashKeys(self, x, y):
        return str((x,y))
    
    def calcSqure(self, x, y, w, h, width, height):
############DEBUG############
        if self.DEBUG:
            print "---IN CALC-SQURE---"
            print "x:" + str(x) + " | y: " + str(y) + " | w: " + str(w) + " | h: " + str(h)
############################## 
        rowNum = width/w
        colNum = height/h
############DEBUG############
        if self.DEBUG:
            print "rowNum:" + str(rowNum) + " | conNum: " + str(colNum)
############################## 
        if (x + w > width):
            x = width - w
        if (y + h > height):
            y = height - h
        Sx = int(x/w)*w
        Sy = int(y/h)*h
#        Sx = (int(x/rowNum)-1)*w
#        Sy = (int(y/colNum)-1)*h
        if Sx < 0:
            Sx = 0
        if Sy < 0:
            Sy = 0
############DEBUG############
        if self.DEBUG:
            print "Square: " + str((Sx, Sy))
############################## 
        return str((Sx, Sy)) 

class problemSquare:
    
    def __init__(self, xStart, yStart, xEnd, yEnd):
        self.xStart = xStart
        self.yStart = yStart
        self.xEnd   = xEnd
        self.yEnd   = yEnd
        self.piles  = set()
        self.robots = set()
        self.distToPiles = 0
        
    '''
    return: ratio piles/robots
    '''
    def calcSquareValue(self, k):
        if len(self.robots) == 0:
            return len(self.piles)
        if len(self.piles) == 0:
            return len(self.robots)
        return abs(float(len(self.piles))/len(self.robots) - k)
    
    def pile2RobotManDist(self):
        '''
        Calculate mannhaten distance in the square
        '''
        if len(self.robots) == 0:
            #no robots
            if  len(self.piles) == 0:
                #no piles
                return 0
            return len(self.piles)
        
        #no piles, but there are robots
        if len(self.piles) == 0:
            return -1
        
        return distToClosestPile(self.robots, self.piles)
        
def distToClosestPile(robots, piles):
    minDist = None
    for pile in piles:
        for robot in robots:
            dist = abs(robot[0] - pile[0]) + abs(robot[1] - pile[1])
            if minDist is None or minDist > dist:
                minDist = dist
    return minDist